package com.demo.java.OD601_650.OD634;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【基站维护最短距离(A卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146963796
 */
public class OdMain {
    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();  // 基站数量
        int[][] matrix = new int[n][n];  // 距离矩阵

        // 读取距离矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = in.nextInt();
            }
        }

        // 调用solve方法计算最短路径
        System.out.println(solve(n, matrix));
    }

    // 动态规划求解TSP问题
    public static int solve(int n, int[][] matrix) {
        int MAX = 1 << n;  // 2^n，表示所有状态的可能性
        int[][] dp = new int[n][MAX];  // dp[i][j]表示从起点出发，经过状态j，最终到达基站i的最短路径

        // 初始化DP数组，所有状态设为一个很大的值
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < MAX; j++) {
                dp[i][j] = n * 500;  // 最大距离是500，初始化为一个较大的值
            }
        }

        // 设置初始状态：从基站0出发
        for (int i = 0; i < n; i++) {
            dp[i][1 << i] = matrix[0][i];  // 初始状态下，从基站0到达其他基站的距离
        }

        // 动态规划状态转移
        for (int j = 0; j < MAX; j++) {  // 遍历每一个状态
            for (int i = 0; i < n; i++) {  // 遍历每一个基站
                if ((j & (1 << i)) == 0) {  // 如果状态j不包含基站i，则跳过
                    continue;
                }
                // 计算从其他基站k到达基站i的最短路径
                for (int k = 0; k < n; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[k][j & ~(1 << i)] + matrix[k][i]);
                }
            }
        }

        // 返回最短路径，即从基站0出发，访问所有基站并返回基站0的最短路径
        return dp[0][MAX - 1];
    }
}